﻿// Roadblocks POJ - 3255.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//

#include <iostream>

using namespace std;
//https://vjudge.csgrandeur.cn/problem/POJ-3255

/*
贝西搬到了一个小农场，有时她喜欢回去看望她的一个好朋友。
她不想太快回到老家，因为她喜欢沿途的风景。她决定走第二短的路，而不是最短的路。
她知道一定有第二条最短的路。
乡村由 R 条（1≤R≤100,000）双向道路组成，每条道路连接 N 个（1≤N≤5000）交叉路口中的两个，
方便地编号为 1...N。贝西从交叉路口 1 出发，她的朋友（目的地）在交叉路口 N。
第二最短路径可以与任何一条最短路径共享道路，也可以回溯，即多次使用同一条道路或交叉路口。
次短路径是长度长于最短路径的最短路径（也就是说，如果存在两条或两条以上的最短路径，则次短路径是长度长于这些路径但不长于任何其他路径的路径）。
输入
第 1 行 两个空格分隔的整数： N 和 R
第 2...R+1 行：每行包含三个空格分隔的整数： 
A、B 和 D 描述一条连接交叉点 A 和 B 且长度为 D 的道路（1 ≤ D ≤ 5000）
输出
第 1 行 节点 1 和节点 N 之间第二条最短路径的长度
样本
输入复制输出复制
4 4
1 2 100
2 4 200
2 3 250
3 4 100
450
提示
两条路线： 1 -> 2 -> 4（长度 100+200=300）和 1 -> 2 -> 3 -> 4（长度 100+250+100=450）。
*/

int main()
{


	return 0;
}

 